백준 11049번

오늘 풀어본 문제는 백준의 11049번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

크기가 $N \times M$ 인 행렬 $A$ 와 $M \times K$ 인 $B$를 곱할 때 필요한 곱셈 연산의 수는 총 $N \times M \times K$ 번이다. 행렬 $N$ 개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, $A$ 의 크기가 $5 \times 3$ 이고, $B$ 의 크기가 $3 \times 2$, $C$ 의 크기가 $2 \times 6$ 인 경우에 행렬의 곱 $ABC$ 를 구하는 경우를 생각해보자.

$AB$ 를 먼저 곱하고 $C$ 를 곱하는 경우 $(AB)C$ 에 필요한 곱셈 연산의 수는 $5 \times 3 \times 2 + 5 \times 2 \times 6 = 30 + 60 = 90$ 번이다.
$BC$ 를 먼저 곱하고 $A$ 를 곱하는 경우 $A(BC)$ 에 필요한 곱셈 연산의 수는 $3 \times 2 \times 6 + 5 \times 3 \times 6 = 36 + 90 = 126$ 번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 $N$ 개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

입력

첫째 줄에 행렬의 개수 $N$ $(1 \leq N \leq 500)$ 이 주어진다.

둘째 줄부터 $N$ 개 줄에는 행렬의 크기 $r$ 과 $c$ 가 주어진다. $(1 \leq r, c \leq 500)$

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 $2^{31}-1$ 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 $2^{31}-1$ 보다 작거나 같다.

풀이과정

1번째 시도

처음 문제를 읽어봤을 때 DP라는 것은 알 수 있었다. 내가 가장 처음으로 생각한 방법은 앞에서 가장 적게 곱해진 횟수를 배열에 저장하고, 두 경우 중 더 적은 횟수로 곱해도 되는 것을 선택하였다.

현재 단계의 바로 앞의 행렬이 더 앞의 행렬들과 곱해진 뒤 현재 행렬과 곱해지는 것

예시: $(ABC)D$
현재 단계의 바로 앞의 행렬이 현재 행렬과 곱해진 뒤 더 앞의 행렬들과 곱해지는 것

예시: $(AB)CD$

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

int dp[501] = { 0, };

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, r, c;
	vector<pair<int, int>> matrixSize(501);

	cin >> N;
	matrixSize.emplace_back(make_pair(0, 0));
	
	for (int i = 1; i <= N; i++) {
		cin >> r >> c;
		if (i == 1) {
			matrixSize[i] = make_pair(r, c);
		}
		else if (i == 2) {
			matrixSize[i] = make_pair(r, c);
			dp[i] = matrixSize[1].first * matrixSize[i].first * matrixSize[i].second;
		}
		else {
			matrixSize[i] = make_pair(r, c);

			int frontFirst, backFirst;

			frontFirst = dp[i - 1] + matrixSize[1].first * matrixSize[i].first * matrixSize[i].second;
			backFirst = dp[i-2] + matrixSize[i-1].first * matrixSize[i].first * matrixSize[i].second + matrixSize[1].first * matrixSize[i - 1].first * matrixSize[i].second;
			dp[i] = min(frontFirst, backFirst);
		}
	}

	cout << dp[N];

	return 0;
}

실행 결과 ‘틀렸습니다’ 가 떴다.

2번째 시도

제출할 때 채점 과정을 보니 퍼센트 표시가 뜨기도 전에 ‘틀렸습니다’가 뜬 것을 보고 이 식에 무언가 치명적인 결함이 있다는 것을 알게되었다. 위에서 예시로 든 $ABCD$ 를 다시 살펴보니 저 2가지 경우 이외에도 $A(BCD)$ 같은 것도 가능하다는 것을 알게된 것이다.

2번째 제출을 하기까지 수정을 총 2번하게 되었는데, 우선 첫 수정에서는 DP 배열의 형태를 바꾸었다. 위와 같은 모든 경우들을 고려하기 위해서는 $m$ 번째 행렬에서 $n$ 번째 행렬까지 곱하는 횟수의 최소 횟수들을 저장해야 했고, 이를 반영하여 코드를 작성하였다.

두 번째 수정에서는 첫 번째 수정에서 작성한 DP 식을 수정하였다. 처음에 썼던 식은 여전히 앞에서 뒤로 쭉 업데이트를 해나가는 방식이었는데, 이 과정에서 아직 계산되지 않은 값들을 이용하여 계산하는 문제점이 있었고, 이를 해결하기 위해 계산할 행렬의 개수를 점점 늘려가면서 앞에서 뒤로 여러 번 이동하도록 식을 작성하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

int dp[501][501] = { 0, };

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;
	vector<pair<int, int>> matrixSize(501);

	cin >> N;
	
	for (int i = 1; i <= N; i++) {
		cin >> matrixSize[i].first >> matrixSize[i].second;
	}

	for (int interval = 1; interval < N; interval++) {
		for (int i = 1; i <= N - interval; i++) {
			int minimum = INT_MAX;

			for (int k = i; k < i + interval; k++) {
				minimum = min(minimum, dp[i][k] + dp[k + 1][i + interval] + matrixSize[i].first * matrixSize[k].second * matrixSize[i + interval].second);
			}

			dp[i][i + interval] = minimum;
		}
	}

	cout << dp[1][N];

	return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

오늘은 처음으로 CLASS 5 문제를 해결한 날이다. 학교 동아리 세미나를 듣고 해결한 2개의 문제들은 모두 CLASS 6 문제들이었기 때문에, CLASS 5 문제는 처음이었다.

문제를 고르는 과정부터 순탄하지 않았는데, 무시무시하게 생긴 문제들이 많았고, 결국 간신히 고른 문제가 이 문제이다. 그리고 확실히 CLASS 4 보다 머리를 더 써야 한다는 느낌을 받을 수 있었다.

현 시점에서는 CLASS 3의 문제도 내가 다 해치워버렸기 때문에 쉬운 문제로 날먹할 수는 없는 상황이다. 그나마 가장 풀 수 있는 쉬운 문제들도 CLASS 4 문제이기 때문에 앞으로 머리를 되게 많이 써야할 것 같은 느낌이 든다… 하지만 이런 고난이 없으면 수행이라고 부를 수 없지 않겠는가? 내일도 열심히 문제들을 풀어보도록 하겠다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/11049

← Previous Post Next Post →